package a00_LeetCode.Tree;

/**
 * @Author quan
 * @Description 从前序与中序遍历序列构造二叉树
 * 给定两个整数preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * @Date 2023/3/29 10:31
 */
public class Num105_ProAndInOrder {
    /**
     * 思想：从前序遍历中找根节点，然后从中序遍历中找到根节点所在的索引位置pos，划分根节点的左右子树。
     * 此时左子树的范围为[0,pos-1]，右子树的范围是[pos+1,数组长度]。递归的传入左右子树不断的找根节点来重建树。
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,inorder,0,inorder.length-1);
    }
    //建立树
    int index = 0;
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        //base case
        //索引越界，刚好指向数组的下一个位置，说明所有节点都处理结束
        if(index == preorder.length){
            return null;
        }
        //如果左区间比右区间大，说明当前中序遍历的[left..right]区间中没有元素
        if(left > right){
            return null;
        }
        //1、先从前序遍历中找到根节点，
        int val  = preorder[index];
        index++;//--------------------------？不理解index的含义
        TreeNode root = new TreeNode(val);
        //2、再中序遍历：找树根的索引位置
        int pos = getIndex(inorder, val);
        //3、根据中序遍历的结果找左右子树
        root.left = buildTreeHelper(preorder,inorder,left,pos-1);
        root.right = buildTreeHelper(preorder,inorder,pos+1,right);
        return root;
    }

    //中序遍历：找树根的索引位置
    private static int getIndex(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if(val == inorder[i]){
                return i;
            }
        }
        return -1;
    }
}
